<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">

<link type="text/css" rel="stylesheet" href="decoration.css">
<title>Geocaching Route Planner</title>
</head>

<body>
<h1>Geocaching Route Planner</h1>

<h2>Introduction</h2>
The purpose of this site is to plan out an optimum route to hit all the caches in a GPX file. 
This is a flavor of the "Traveling Salesman Problem" that is the source of much research because of the complexity of
trying to come up with a "tour" that does not require hitting a location more than once.<p/>

<h2>Purpose</h2>
The site takes a GPX file and create a set of driving or walking instructions based on Google Maps.<p/>
<br/>
This site is meant to serve as a fun and informal research tool for designing TSP algorithms, with the bigger purpose
of caching more efficiently. Please enjoy, but know that the TSP is a non-trivial problem, so
the results of this program <i>may</i> seem quite puzzling, leaving you to ask "Why would it suggest I do that?"<p/>

<div class="note">This site does not exist for any financial gain. No personal information is required.</div><p/>

All of the <a href="http://code.google.com/p/geotripplanner/">code</a> for this site is available for viewing. If you would
like to help, in any capacity, please send me an email and I will add you to the list of committers.<p/>

Everything here is still under development, so if you come across a problem, please create a <a href="http://code.google.com/p/geotripplanner/">bug report</a>.<p/> 

<h2>Algorithms Used</h2>
There are two algorithms currently being used, <b><i><a href="http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm">Nearest Neighbor</a></i></b> 
and <b><i>NaiveFrog</i></b>.<p/>
Nearest Neighbor is a common algorithm and is better explained in the Wikipedia link above. NaiveFrog is a home-grown 
algorithm that attempts to be more "cacher-friendly" than traditional TSP algorithms. 
<h3>NaiveFrog</h3>
The NaiveFrog algorithm assumes that the cacher is standing in the middle of four connecting squares. Each cache is placed in one of the 
four quadrants based on its position from the cacher (in the current implementation, the cacher is standing on the first cache in the 
GPX file, though I will change this to be a separate input box). The four quadrants are based on the compass rose: NW, NE, SW, SE. <p/>

The Nearest Neighbor algortihm is then applied to the caches in each of the quadrants, starting in the NW quadrant, then moving NE,
SE, then SW, making a circle. Then the optimized lists are chained together, in the same direction. Thus the cacher is guaranteed to
have an optimum tour (as far as Nearest Neighbor allows) in each of the four quadrants. <p/>

The reason why the algorithm is called NaiveFrog is because of its simplistic nature in assuming that the cacher wants to move
in a clockwise fashion, starting from NW, as well as the fact that the Nearest Neighbor can not necessarily figure out the "best"
tour; it only tries to find the closest cache next to the current one. The frog part comes in because of the geocaching mascot. <p/>

<p/>
<div class="upload">Upload the file below.</div><br/> 
<div class="uploadwarning">(It should be in GPX file format)</div><p/>

<form method="post" enctype="multipart/form-data"
	action="routeplanner">
<table>
	<tr>
		<td><input type="file" size=20 name="fname"></td>
		<td><input type="Submit" value="Upload"></td>
	</tr>
</table>
</form>
</table>
</body>
</html>
